Fidélité du système RSA

Propriété

Soit $p$ et $q$ deux nombres premiers distincts. On note $N=pq$ et $n=(p-1)(q-1)$ .

Soit $c$ un entier tel que \(1 \leqslant c et $\mathrm{PGCD}(c;n)=1$ . Alors

1. il existe un unique entier $d$ tel que \(1 \leqslant d et $cd\equiv 1[n]$ ;

2. pour tous $a$ , $b\in \mathbb{N}$ , si $b\equiv a^c[N]$ , alors $a\equiv b^d[N]$ ; autrement dit $a^{cd}\equiv a[N]$ .

Remarque

Le second point de la propriété précédente assure qu'à l'étape de décodage du message par le destinataire, il obtient $b^{\prime }\equiv a^{cd}\equiv a[N]$ .
Ainsi, le destinataire retrouve bien le message original envoyé par l'expéditeur. Cela justifie la fidélité du codage RSA.